let arr1 = [10, 23, 2, 3, 4, 222, 4444, 222222]


// function bubbleSort(list) {
//   var n = list.length;
//   if (!n) return [];

//   for (var i = 0; i < n; i++) {
//     // 注意这里需要 n - i - 1
//     for (var j = 0; j < n - i - 1; j++) {
//       if (list[j] > list[j + 1]) {
//         var temp = list[j + 1];
//         list[j + 1] = list[j];
//         list[j] = temp;
//       }
//     }
//   }
//   return list;
// }
// // console.log(bubbleSort(arr));

// function jsQuickSort(array) {
//   if (array.length <= 1) {
//     return array;
//   }
//   const pivotIndex = Math.floor(array.length / 2);
//   const pivot = array.splice(pivotIndex, 1)[0];  //从数组中取出我们的"基准"元素
//   const left = [], right = [];
//   array.forEach(item => {
//     if (item < pivot) {  //left 存放比 pivot 小的元素
//       left.push(item);
//     } else {  //right 存放大于或等于 pivot 的元素
//       right.push(item);
//     }
//   });
//   //至此，我们将数组分成了left和right两个部分
//   return jsQuickSort(left).concat(pivot, jsQuickSort(right));  //分而治之
// }
// console.log(jsQuickSort(arr));


// function maopao(arr) {
//   for (let i = 0; i < arr.length; i++) {
//     for (let j = 0; j < arr.length - i - 1; j++) {
//       if (arr[j] > arr[j + 1]) {
//         let temp = arr[j + 1]
//         arr[j] = arr[j + 1]
//         arr[j + 1] = temp
//       }
//     }
//   }
//   return arr
// }
// console.log(maopao(arr1));

// function kuaiPai(arr) {
//   if (arr.length <= 1) {
//     return arr;
//   }
//   let middle = Math.floor(arr.length / 2)
//   let left = [];
//   let right = [];
//   debugger
//   let middleNum = arr.splice(middle, 1)[0]
//   arr.map(item => {
//     if (item < middleNum) {
//       left.push(item)
//     } else {
//       right.push(item)
//     }
//   })
//   return kuaiPai(left).concat(middleNum, kuaiPai(right))
// }


let arr = [3, 2, 11, 3]
function kuaiPai(arr) {
  if (arr.length <= 1) return arr
  // 取中间数
  let middleIndex = Math.floor(arr.length / 2);
  let middleNum = arr.splice(middleIndex, 1)[0];
  let left = []
  let right = []

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < middleNum) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return kuaiPai(left).concat(middleNum, kuaiPai(right));
}
console.log(kuaiPai(arr1));